package practice_2025_11.practice_11_20;

import java.util.Arrays;

class Solution {
    /**
     * 设置交集大小至少为2
     * 排序 + 贪心
     * 在数轴上选出尽可能少的整数点，使得每个区间都至少包含两个点
     * 排序 [a, b]：(优先保证小区间: 右端点越小的区间“可操作空间”越少，应优先满足；当右端点相同时，左端点更大的区间更窄，更应优先被处理)
     * 1. 按右端点 b 从小到大
     * 2. 当右端点 b 相同时，按左端点 a 从大到小
     * 两个点 {s, e}
     * 依次处理区间 [a, b]：
     * a <= s:区间内包含两个点
     * s < a <= e: 区间内只包含 e 一个点，需要补一个点(res += 1), 且更新 {e, b}
     * a > e: 区间内两个点都不包含，需要补两个点(res += 2), 更新 {b - 1, b}
     */
    public int intersectionSizeTwo(int[][] intervals) {
        // 将二维数组升序排列
        Arrays.sort(intervals, (a, b) -> {
            if (a[1] == b[1]) {
                return b[0] - a[0];
            }
            return a[1] - b[1];
        });
        int s = -1, e = -1; // s: 第一个点 e: 第二个点
        int res = 0;
        for(int i = 0; i < intervals.length; i++) {
            // 区间内不包含已有两个点
            if (intervals[i][0] > e) {
                res += 2;
                s = intervals[i][1] - 1;
                e = intervals[i][1];
            } else if (intervals[i][0] <= s) {
                // 区间内包含已有两个点
            } else {
                // 区间内只包含一个点 e
                res += 1;
                s = e;
                e = intervals[i][1];
            }
        }
        return res;

    }
}